package com.yehui.algorithm.sword;

import java.util.ArrayList;

/**
 *输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
 * Created by XuChunH on 2016/9/18.
 */
public class FindNumbersWithSum {

    public ArrayList<Integer> solution(int[] array, int sum){
        ArrayList<Integer> result = new ArrayList<>();
        if(array == null || array.length == 0) {
            return result;
        }
        int i = 0;
        int j = array.length - 1;
        while (i < j) {
            if(array[i] + array[j] == sum) {
                result.add(array[i]);
                result.add(array[j]);
                break;
            }
            while (i < j && array[i] + array[j] > sum) {
                j--;
            }
            while (i < j && array[i] + array[j] < sum) {
                i++;
            }
        }
        return result;
    }

}
